Intuiting the Algorithms Behind Permutations and Combinations
Permutations and combinations are a popular class of computer science problems usually solved (and taught) with recursion, but I think recursion is an unnatural starting point for learning permutations/combinations for people who spend most of their time writing loops. You might see an existing recursive solution and start thinking about what the code is doing on the 2nd call, then notice that 2nd call branches off to several more calls and suddenly you've lost track of the original call or how the results join together. Books/videos/teachers will tell you not to try and trace the algorithm and just trust it instead – but if you can't convince yourself of what it's doing then you may never feel comfortable trusting it.
The typical guidance for finding a recursive solution is to “solve the base case and build,” i.e. break the problem into smaller chunks (subproblems) and solve for n=1, then n=2, then n=3 and by then everything should “just work” but if this isn't intuitive, then you may not feel comfortable “trusting it.” It's probably because you don't have a mental model for what happens when you start recursing. You can improve your mental model by visualizing various DFS or BFS through a tree or the equivalent algorithm as a series of nested for loops – so here are the iterative solutions to a few combinatorics problems, in Ruby, to help jumpstart a mental model. Note, when using nested for loops, our solution is limited (read: hard coded) in what inputs it can take as opposed to a recursive solution which is limited by the size of the call stack.
Repeated Permutation
- The Ruby stdlib solution
%W(a b c d).repeated_permutation(4).to_a
This is the simplest, mere nested for loops... but very slow: o(nn) - exponential
Note the existence of 4 nested loops means
this is hardcoded for an array of size 4
# n**n
# 4 nested loops for array of size 4
def repeated_permutation(arr = %W(a b c d))
res = []
arr.each do |c1|
arr.each do |c2|
arr.each do |c3|
arr.each do |c4|
res << [c1, c2, c3, c4]
end
end
end
end
res
end
# don't pass any args since this nested
# loop solution is hardcoded for input
# of size 4
repeated_permutation()
def repeated_permutation(arr, depth=0)
return [[]] if depth == arr.size
res = []
arr.each do |c|
res.concat repeated_permutation(arr, depth+1).map{|p|p.unshift c}
end
res
end
repeated_permutation(%W(a b c d))
Non-repeated Permutation
- The Ruby stdlib solution
%W(a b c d).permutation.to_a
This is the same as the repeated permutation except we reduce the size of the array on each nest/recurse - once we've used a character from the set, we cannot use it on any nested loops/recurses below. Still very slow o(n!), but slightly faster than repeated permutations.
Note the existence of 4 nested loops means this
is hardcoded for an array of size 4
# n! (4 nested loops for array of size 4)
def permutation(arr = %W(a b c d))
res = []
# returns new array without element at index i
without = -> (a, i) { a[0...i] + a[(i+1)..-1] }
arr.size.times do |i|
c1 = arr[i]
c2_arr = without.call(arr, i)
c2_arr.size.times do |j|
c2 = c2_arr[j]
c3_arr = without.call(c2_arr, j)
c3_arr.size.times do |k|
c3 = c3_arr[k]
c4_arr = without.call(c3_arr, k)
c4_arr.size.times do |l|
c4 = c4_arr[l]
res << [c1, c2, c3, c4]
end
end
end
end
res
end
# don't pass any args since this nested loop solution
# is hardcoded for input of size 4
permutation()
Note: I'm slicing the array multiple times in this example for readability: arr[1..-1] which adds o(n) time on each slice operation where n is the size of the new array - but the same code could be rewritten by tracking indices and swapping instead.
def permutation(arr)
return [[]] if arr.empty?
# returns new array without element at index i
without = -> (a, i) { a[0...i] + a[(i+1)..-1] }
res = []
arr.each_with_index do |c, i|
res.concat permutation(without.call(arr,i)).map{|perm| perm.unshift c}
end
res
end
# can pass any array
permutation(%W(a b c d))
Combinations (n choose k)
- The Ruby stdlib solution
%W(a b c d e).combination(3).to_a
nest or recurse k times where each of those levels loops over a set of elements of size n-k and on shifts that set of elements to the right for the next level
a b c d e
a b c d e
a b c d e
abc, abd, abe
second result set (dives depth of 3 (or k))
a b c d e
a b c d e
a b c d e
acd, ace
third result set (dives depth of 3 (or k))
a b c d e
a b c d e
a b c d e
ade
fourth result set (dives depth of 3 (or k))
a b c d e
a b c d e
a b c d e
bcd, bce
fifth result set (dives depth of 3 (or k))
a b c d e
a b c d e
a b c d e
bde
sixth result set (dives depth of 3 (or k))
a b c d e
a b c d e
a b c d e
cde
Note: the existence of only 2 nested loops
means this is hardcoded for k = 2 (so this
code can only support k of 2, but arr can be
any size)
# 2 nested loops for k of 2
# time complexity is n choose k (number of
# combinations)
# n choose k = n!/(k!*(n-k)!), so between
# n log n and n^2
def combination(arr = %W(a b c d e), k = 2)
res = []
# stop at -2 (2nd from last) because the
# nested loop covers that if k was 3, then
# we'd stop at -3 and have 3 total loops
arr[0..-2].each_with_index do |c1, i1|
arr[(i1+1)..-1].each do |c2|
res << [c1, c2]
end
end
res
end
# don't pass any args since they have to be
# hardcoded
combination()
Note: I'm slicing the array in this example for readability: arr[1..-1] which adds o(n) time to each iteration where n is the size of the new array - but the same code could be rewritten by tracking indices instead.
def combination(arr, k)
return [[]] if k == 0
res = []
arr[0..(0-k)].each_with_index do |c, i|
res.concat combination(arr[(i+1)..-1], k-1).map{|combo| combo.unshift(c)}
end
res
end
combination(arr=%W(a b c d e), k=3)
Variations of the combinations algo: knapsack, change-making (combinatorial optimization)
These are popular problems where order doesn't matter (combination as opposed to permutation) and you're optimizing for a single value (dollar amount), or multiple values (dollar amount and weight)
· knapsack unbounded: given a set of item types where each item has a weight and value, find the combination of those types (with any amount of repetition) that has the maximum value
· knapsack 0/1: given a set of items where each item has a weight and value, find the combination of those that has the maximum value
· change-making: given a set of coins, find all combinations (with repetitions) that add up to some amount.
The brute force recursion solution for these are simple variations on the combination algo where the base case is changed to ensure you haven't exceeded a dollar amount or weight value - but the optimum solution involves dynamic programming (avoidance of solving the same problem over and over again) by caching/memoizing subproblems.
